home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Language/OS - Multiplatform Resource Library
/
LANGUAGE OS.iso
/
pcr
/
pcr4_4.lha
/
DIST
/
gc
/
GCmark_rescuers.c
< prev
next >
Wrap
C/C++ Source or Header
|
1991-05-29
|
13KB
|
448 lines
/* begincopyright
Copyright (c) 1988,1990 Xerox Corporation. All rights reserved.
Use and copying of this software and preparation of derivative works based
upon this software are permitted. Any distribution of this software or
derivative works must comply with all applicable United States export
control laws. This software is made available AS IS, and Xerox Corporation
makes no warranty about the software, its performance or its conformity to
any specification. Any person obtaining a copy of this software is requested
to send their name and post office or electronic mail address to:
PCR Coordinator
Xerox PARC
3333 Coyote Hill Rd.
Palo Alto, CA 94304
Parts of this software were derived from code bearing the copyright notice:
Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
This material may be freely distributed, provided this notice is retained.
This material is provided as is, with no warranty expressed or implied.
Use at your own risk.
endcopyright */
/*
* Boehm, December 28, 1990
*/
# include "xr/GCPrivate.h"
# ifdef PRINTSTATS
static long rescuers = 0;
# endif
# define MIN_MARK_SZ 10000 /* Minimum number of objects to mark at once */
/* Push all possible pointers from marked objects in the given block onto */
/* the mark stack. */
/* This is the general version. */
static void GC_mark_block(hbp, sz)
register struct hblk * hbp;
register long sz;
{
register word * q;
register word * p;
register word * plim;
register word potential_ptr;
register int word_no;
# ifdef PRINTSTATS
register long rescuers_reg = 0;
# endif
# ifdef SEPARATE_HEADERS
register struct hblkhdr * hhdr = HDR(hbp);
# define MARK_BIT(word_no) mark_bit_from_hdr(hhdr, word_no)
# else
# define MARK_BIT(word_no) mark_bit(hbp, word_no)
# endif
/* Register copies of frequently referenced globals */
/* Referenced primarily from inside macros. */
register char * GC_heapstart_reg = GC_heapstart;
register word * GC_mark_stack_top_reg = GC_mark_stack_top;
# define GC_heapstart GC_heapstart_reg
p = (word *)(hbp->hb_body);
word_no = HDR_WORDS;
plim = (word *)((((unsigned)hbp) + HBLKSIZE)
- WORDS_TO_BYTES(sz));
do {
if (MARK_BIT(word_no)) {
# ifdef PRINTSTATS
rescuers_reg++;
# endif
# ifdef VISUALIZE
displayRoot(p, sz);
# endif
/* Copy potential pointers into mark stack */
/* and increment p by sz. */
/* This is time critical and therefore */
/* done without calling GC_mark_all or the */
/* like. */
q = p;
p += sz - 1;
while(q <= p) {
potential_ptr = *q;
if (quicktest(potential_ptr)) {
# define GC_mark_stack_top GC_mark_stack_top_reg
PUSH_MS(potential_ptr);
# undef GC_mark_stack_top
}
# ifdef UNALIGNED
q = (word *)(((char *)q) + alignment);
# else
q++;
# endif
}
p++;
} else {
p += sz;
}
word_no += sz;
} while (p <= plim);
GC_mark_stack_top = GC_mark_stack_top_reg;
# ifdef PRINTSTATS
rescuers += rescuers_reg;
# endif
# undef GC_heapstart
}
/* What follows are versions of the above specialized for different object */
/* sizes. They assume 4 byte pointer alignment. */
/* They also assume that BODY_SZ is a multiple of 32. */
/* A version for sz > MAXOBJSZ. Looks at dirty bits of successive pages. */
/* Not that the first page will always be scanned since it is set if any */
/* of the subsequent pages are dirty. */
/* Index is the index of the first page in the GC_dirty_bits array. */
static void GC_mark_large_block(hbp, sz, index)
register struct hblk * hbp;
register long sz;
register long index;
{
register word q;
register word * p;
register word * plim;
register word * limit;
/* Register copies of frequently referenced globals */
/* Referenced primarily from inside macros. */
register char * GC_heapstart_reg = GC_heapstart;
register word * GC_mark_stack_top_reg = GC_mark_stack_top;
# define GC_heapstart GC_heapstart_reg
if (!mark_bit(hbp, HDR_WORDS)) return;
p = (word *)(hbp->hb_body);
limit = p + sz;
rescuers++;
# ifdef VISUALIZE
displayRoot(p, sz);
# endif
do {
plim = (word *)(((unsigned)p + HBLKSIZE) & ~HBLKMASK);
if (plim > limit) plim = limit;
if (GC_dirty_bits[index]) {
for(; p < plim; p += 2) {
# define GC_mark_stack_top GC_mark_stack_top_reg
q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
# undef GC_mark_stack_top
}
} else {
p = plim;
}
index++;
} while (p < limit);
if (sz & 1) {
/* We unrolled inner loop once. We may have to remove the */
/* superfluous element pushed as a result. */
if (*limit == *GC_mark_stack_top_reg
&& GC_mark_stack_top_reg != GC_mark_stack_top) {
/* TOS must be copy of superfluous entry, since all stack */
/* elements satisfy quicktest. */
# ifdef USE_STACK
GC_mark_stack_top_reg++;
# else
GC_mark_stack_top_reg--;
# endif
}
}
GC_mark_stack_top = GC_mark_stack_top_reg;
# undef GC_heapstart
}
/* For 2 word objects */
static void GC_mark_block_2(hbp)
register struct hblk * hbp;
{
register word * p;
register word * plim;
register word q;
register long marks;
register long * marks_addr;
register word * GC_mark_stack_top_reg = GC_mark_stack_top;
register char * GC_heapstart_reg = GC_heapstart;
# define GC_heapstart GC_heapstart_reg
register int i;
# ifdef PRINTSTATS
register long rescuers_reg = 0;
# endif
p = (word *)(hbp->hb_body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
marks_addr = hb_marks(hbp);
do {
marks = *marks_addr++;
if (marks != 0) {
for (i = 0; i < WORDSZ; i += 2, p+= 2) {
if ((marks >> i) & 1) {
# ifdef PRINTSTATS
rescuers_reg++;
# endif
# ifdef VISUALIZE
displayRoot(p, 2);
# endif
# define GC_mark_stack_top GC_mark_stack_top_reg
q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
# undef GC_mark_stack_top
}
}
} else {
p += WORDSZ;
}
} while (p < plim);
GC_mark_stack_top = GC_mark_stack_top_reg;
# ifdef PRINTSTATS
rescuers += rescuers_reg;
# endif
# undef GC_heapstart
}
/* For 4 word objects */
static void GC_mark_block_4(hbp)
register struct hblk * hbp;
{
register word * p;
register word * plim;
register word q;
register long marks;
register long * marks_addr;
register word * GC_mark_stack_top_reg = GC_mark_stack_top;
register char * GC_heapstart_reg = GC_heapstart;
# define GC_heapstart GC_heapstart_reg
register int i;
# ifdef PRINTSTATS
register long rescuers_reg = 0;
# endif
p = (word *)(hbp->hb_body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
marks_addr = hb_marks(hbp);
do {
marks = *marks_addr++;
if (marks != 0) {
for (i = 0; i < WORDSZ; i += 4, p+= 4) {
if ((marks >> i) & 1) {
# ifdef PRINTSTATS
rescuers_reg++;
# endif
# ifdef VISUALIZE
displayRoot(p, 4);
# endif
# define GC_mark_stack_top GC_mark_stack_top_reg
q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
q = p[2]; if (quicktest(q)) { PUSH_MS(q); }
q = p[3]; if (quicktest(q)) { PUSH_MS(q); }
# undef GC_mark_stack_top
}
}
} else {
p += WORDSZ;
}
} while (p < plim);
GC_mark_stack_top = GC_mark_stack_top_reg;
# ifdef PRINTSTATS
rescuers += rescuers_reg;
# endif
# undef GC_heapstart
}
/* For 8 word objects */
static void GC_mark_block_8(hbp)
register struct hblk * hbp;
{
register word * p;
register word * plim;
register word q;
register long marks;
register long * marks_addr;
register word * GC_mark_stack_top_reg = GC_mark_stack_top;
register char * GC_heapstart_reg = GC_heapstart;
# define GC_heapstart GC_heapstart_reg
register int i;
# ifdef PRINTSTATS
register long rescuers_reg = 0;
# endif
p = (word *)(hbp->hb_body);
plim = (word *)(((unsigned)hbp) + HBLKSIZE);
marks_addr = hb_marks(hbp);
do {
marks = *marks_addr++;
if (marks != 0) {
for (i = 0; i < WORDSZ; i += 8, p+= 8) {
if ((marks >> i) & 1) {
# ifdef PRINTSTATS
rescuers_reg++;
# endif
# ifdef VISUALIZE
displayRoot(p, 8);
# endif
# define GC_mark_stack_top GC_mark_stack_top_reg
q = p[0]; if (quicktest(q)) { PUSH_MS(q); }
q = p[1]; if (quicktest(q)) { PUSH_MS(q); }
q = p[2]; if (quicktest(q)) { PUSH_MS(q); }
q = p[3]; if (quicktest(q)) { PUSH_MS(q); }
q = p[4]; if (quicktest(q)) { PUSH_MS(q); }
q = p[5]; if (quicktest(q)) { PUSH_MS(q); }
q = p[6]; if (quicktest(q)) { PUSH_MS(q); }
q = p[7]; if (quicktest(q)) { PUSH_MS(q); }
# undef GC_mark_stack_top
}
}
} else {
p += WORDSZ;
}
} while (p < plim);
GC_mark_stack_top = GC_mark_stack_top_reg;
# ifdef PRINTSTATS
rescuers += rescuers_reg;
# endif
# undef GC_heapstart
}
/* Mark all objects reachable from previously marked objects on dirty pages */
void GC_mark_rescuers(alignment)
int alignment;
{
register long i,j;
struct hblk * hbp;
unsigned long limit = divHBLKSZ(GC_heaplim - GC_heapstart);
long sz;
word * plim;
# ifdef PRINTSTATS
long dirty_pages = 0;
# endif
/* Register copies of frequently referenced globals */
/* Referenced primarily from inside macros. */
register char * GC_heapstart_reg = GC_heapstart;
# define GC_heapstart GC_heapstart_reg
/* Difference in starting point of hblkmap and GC_dirty_bits arrays */
register unsigned long offset = divHBLKSZ(GC_heapstart - VD_base);
# ifdef PRINTSTATS
rescuers = 0;
# endif
/* Make sure mark stack is empty */
if (GC_mark_stack_top != GC_mark_stack_bottom) {
GC_abort("GC_mark_rescuers 0");
}
if (GC_my_objects_in_use == 0) {
/* Nothing has been marked yet. It's safe to skip this */
return;
}
for (i = 0; i < limit; i++) {
if (hblkmap[i] == HBLK_VALID && GC_dirty_bits[i + offset]) {
hbp = (struct hblk *)(HBLKSIZE * i + GC_heapstart);
sz = hb_sz(hbp);
if (sz < 0) {
/* Atomic. There cant be any rescuers here. */
continue;
}
# ifdef PRINTSTATS
dirty_pages++;
# endif
# if defined(UNALIGNED) || !defined(SEPARATE_HEADERS) \
|| ALIGNED_DISCARD_WORDS != 0
GC_mark_block(hbp, sz);
# else
switch(sz) {
case 2:
GC_mark_block_2(hbp);
break;
case 4:
GC_mark_block_4(hbp);
break;
case 8:
GC_mark_block_8(hbp);
break;
default:
if (sz > MAXOBJSZ) {
GC_mark_large_block(hbp, sz, i + offset);
} else {
GC_mark_block(hbp, sz);
}
}
# endif
/* Mark what's currently on the stack, provided there's */
/* enough there. */
# ifdef USE_STACK
if (GC_mark_stack_bottom - GC_mark_stack_top
>= MIN_MARK_SZ) {
GC_mark(alignment);
}
# else
if (GC_mark_stack_top - GC_mark_stack_bottom
>= MIN_MARK_SZ) {
GC_mark(alignment);
}
# endif
}
}
/* Mark anything still left to be marked at the end. Clean up */
/* the mark stack. */
if (GC_mark_stack_top != GC_mark_stack_bottom) GC_mark(alignment);
# ifdef USE_HEAP
brk(GC_mark_stack_bottom); /* reset break to where it was before */
GC_cur_break = (char *) GC_mark_stack_bottom;
# endif
# ifdef VISUALIZE
/* remove root display */
for (i = 0; i < MAP_SIZE; i++) {
if (hblkmap[i] == HBLK_VALID && GC_dirty_bits[i+offset]) {
hbp = (struct hblk *)(HBLKSIZE * i + GC_heapstart);
sz = hb_sz(hbp);
if (sz < 0) {
continue;
}
if (sz > MAXOBJSZ &&
mark_bit(hbp, (hbp -> hb_body) - ((word *)(hbp))) ) {
displayMark(hbp -> hb_body, sz);
} else {
/* Small composite objects */
p = (word *)(hbp->hb_body);
word_no = p - ((word *)hbp);
plim = (word *)((((unsigned)hbp) + HBLKSIZE)
- WORDS_TO_BYTES(sz));
for (; p <= plim; p += sz, word_no += sz) {
if (mark_bit(hbp, word_no)) {
displayMark(p, sz);
}
}
}
}
}
# endif
# ifdef PRINTSTATS
GC_printf("%d dirty composite pages, %d potentially rescuing objects\n",
dirty_pages, rescuers);
# endif
}